package demo1;

public class HashBucket {
    private static class Node {
        private int key;
        private int value;
        Node next;


        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }


    private Node[]  array;
    private int size;   // 当前的数据个数
    private static final double LOAD_FACTOR = 0.75;
    private static final int DEFAULT_SIZE = 10;//默认桶的大小

    public int put(int key, int value) {
        int index = key % array.length;
        Node node = new Node(key, value);
        Node cur = array[index];
        Node prev = null;
        while(cur != null) {
            if(cur.key == key) {
                cur.value = value;
                return -1;
            }
            prev = cur;
            cur = cur.next;
        }
        // 此时 prev 不是 cur 的上一个就是 null
        if(prev == null) {
            array[index] = node;
        } else {
            prev.next = node;
        }
        size++;
        double factor = loadFactor();
        if(factor > LOAD_FACTOR) {
            // 需要重新加载
            resize();
        }
        return 1;
    }



    private void resize() {
        Node[] tmpArr = new Node[array.length + (array.length >>> 1)];
        // 遍历原链表
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while(cur != null) {
                Node next = cur.next;// cur 的下一个节点 防止找不到

                // 添加到新的链表
                int indexTmp = cur.key % tmpArr.length;
                Node tmpNode = tmpArr[indexTmp];
                Node tmpPrev = null;
                while(tmpNode != null) {
                    tmpPrev = tmpNode;
                    tmpNode = tmpNode.next;
                }
                if(tmpPrev == null) {
                    tmpArr[indexTmp] = cur;
                } else {
                    tmpPrev.next = cur;
                }
                cur.next = null;// 都将当前节点的下一个置为 null

                cur = next;
            }
        }
        array = tmpArr;
    }


    private double loadFactor() {
        return size * 1.0 / array.length;
    }


    public HashBucket() {
        array = new Node[DEFAULT_SIZE];
    }


    public int get(int key) {
        // write code here
        int index = key % array.length;
        Node node = array[index];
        while(node != null) {
            if(node.key == key) {
                return node.value;
            }
            node = node.next;
        }
        return -1;
    }
}
